/******************************************************
 *  Project： 
 *  Function:
 *  Description: ${description}
 *  PROJECT_FILENAME: ${PROJECT_FILENAME}
 *  Author: coder-itl
 ******************************************************
 *  Copyright $NOW_L by coder-itl
 ******************************************************/

// #include "HaFuManTree.h"
#include <stdio.h>
#include <stdlib.h>

#define N 20
#define M 2*N-1
typedef struct {
    int weight;
    int parent;
    int leftChild;
    int rightChild;
} HaffmanNode, HaffmanTree[M + 1];
typedef char *HaffmanCode[N+1];

void select(HaffmanTree ht, int i, int *s1, int *s2);

void CreateHalffmanTree(HaffmanTree ht, int *w, int n);

int main() {
    HaffmanTree tree;
    int length;
    scanf("%d", &length);
    int nodeArray[length + 1];

    /* 如何存储权重到指定节点上:
     *
     * */
    // 【输入形式】输入叶子结点的个数以及对应权值。

    //  【输出形式】显示结点序号，输出哈夫曼树的静态三叉链表（序号后面加冒号，静态三叉链表中元素之间用空格隔开，每个结点占一行）；显示叶子结点的权值和对应的编码（叶子结点的权值后面加冒号，每个编码占一行）。

    for (int i = 1; i <= length; i++) {
        /* 创建哈弗曼树,权重 */
        scanf("%d", &nodeArray[i]);
    }
    CreateHalffmanTree(tree, nodeArray, length);

    return 0;
}

void CreateHalffmanTree(HaffmanTree ht, int w[], int n) {
    int i, m, s1, s2;
    for (i = 1; i <= n; i++) {
        ht[i].weight = w[i];
        ht[i].parent = 0;
        ht[i].leftChild = 0;
        ht[i].rightChild =0;
    }

    m = 2 * n - 1;
    for (i = n + 1; i <= m; i++) {
        ht[i].weight = 0;
        ht[i].parent = 0;
        ht[i].leftChild = 0;
        ht[i].rightChild = 0;
    }

    for (i = n + 1; i <= m; i++) {
        select(ht, i - 1, &s1, &s2);

        ht[i].weight = ht[s1].weight + ht[s2].weight;
        ht[s1].parent = i;
        ht[s2].parent = i;
        ht[i].leftChild = s1;
        ht[i].rightChild = s2;
    }
}

/* 查找 1 - (i-1) */
void select(HaffmanTree ht, int n, int *s1, int *s2) {
    int i;
    int min1 = 100;
    int min2 = 100;

    for (i = 1; i <=n ; i++) {
        if(i!=(*s1) && ht[i].parent==0){
            if(min2>ht[i].weight){
                min2 = ht[i].weight;
                *s2 = i;
            }
        }
    }

}

void CrtHuffmanCode(HaffmanTree ht,HaffmanCode hc,int n){
    int i,c,p,start;
    char *cd;
    cd = ( char*) malloc((n*sizeof (char )));
    cd[n-1] = '\0';
    for (int j = 0; j < ; ++j) {
        
    }
}